package com.freedy.algorithm.dijkstra;

import java.util.Arrays;

/**
 * @author Freedy
 * @date 2021/4/13 21:50
 */
public class MGraph {
    int verxs;//节点的个数
    char[] data;//存放在节点的数据
    int[][] weight;//存放边，就是我们的邻接矩阵


    public MGraph(char[] data, int[][] weight) {
        if (data.length!=weight.length||weight[0].length!=weight.length)
            throw new RuntimeException("传入的数据不匹配!");
        this.verxs = data.length;
        this.data=data;
        this.weight=weight;
    }

    public void printGraph(){
        for (int i = -1; i < weight.length; i++) {
            for (int j = -1; j < weight[0].length; j++) {
                if (i==-1){
                    System.out.print(j==-1?"  ":data[j]+" ");
                }else if (j==-1){
                    System.out.print(data[i]+" ");
                } else {
                    System.out.print(weight[i][j]+" ");
                }
            }
            System.out.println();
        }
    }

    /**
     * index表示触发点的下标
     * @param index
     */
    public void dsj(int index){
        VisitedVertex vertex = new VisitedVertex(verxs,index);
        int temp=index;
        for (int i = 0; i < verxs; i++) {
            index=vertex.updateArr();
            update(index,vertex);
        }
        printDsjResult(temp,vertex);
    }
    
    private void update(int index,VisitedVertex vertex){
        int len=0;
        for (int i = 0; i < verxs; i++) {
            if (weight[index][i]>0){
                len=vertex.getDis(index)+weight[index][i];
                if (!vertex.isVisited(i)&&len<vertex.getDis(i)){
                    vertex.updateDis(i,len);
                    vertex.updatePaths(index,i);
                }
            }
        }
    }

    private void printDsjResult(int index,VisitedVertex vertex){
        int[][] paths = vertex.getPaths();
        for (int i = 0; i < paths.length; i++) {
            System.out.print(data[index]+"->"+data[i]+"的路径为:");
            StringBuilder pathStr=new StringBuilder();
            for (int j = 0; j < paths[i].length; j++) {
                if (paths[i][j]!=-1){
                    pathStr.append(data[paths[i][j]]).append("->");
                }
            }
            pathStr.delete(pathStr.length()-2,pathStr.length());
            pathStr.append("总长度为:");
            pathStr.append(vertex.getDis(i));
            System.out.println(pathStr);
        }
    }
}
